プロアクティブ秘密分散法:PSS(Proactive Secret Sharing)
1. PSSの概要
PSSのはSSSを踏襲したものであり「Shareの再シャッフルを可能にする」ことができるのでメンバーが増減したり、shareの一部が紛失した(ハードウェアの破損など)ユーザが再度グループに復帰するような場合を想定したときにPSSは有効。
さらに、ディーラが存在しないためブロックチェーンのような非中央集権的システムに適してる
SSSに検証可能性を追加したのがVSS、さらに再分配を可能にし、ディーラーを廃したのがPSS
例:アリスのコンピューターが危険にさらされた
このとき、PSSは以下の条件を満たす。
(1)ボブ/キャロル/デイブは共有を再シャッフルして、アリスの共有を廃止したい
(2)アリスが後で新しいコンピューターを購入し、メンバーに復帰したい
(3)最初に秘密を再構築せずにshareを再分配したい
この再シャッフルの過程で、SSSのように信頼できるディーラーが存在した場合、他のメンバーは自分の鍵をディーラーに送り、ディーラーは秘密を再構築し、新しい多項式を生成し、新しいshareを彼らに配布する。
ディーラーは、後で新しいコンピューターを持っているときに、新しいシェアをアリスに送信することもできる。
しかし、分散的環境では再構築の権利を第三者に委ねるのはリスクを生じる
2. 多項式の追加
PSSではSSSと同じように、多項式を使ってshareを作成し、ラグランジュ補間公式で復元する。
再分配のアイデアは「SSSの多項式に再分配の多項式を追加する」というもの
例:secret=5の(1,2)閾値分散の多項式にボブがshareを追加する
以下の２次多項式上にshareが存在するとする
$ f(x)=x^2-4x+5
ボブはこれに対して、$ g(0)=0を満たす
$ g(x)=x^2-2x
を追加する。従って
$ f'(x)=f(x)+g(x)=2x^2-6x+5
が新しく作成される。
このとき、$ g(0)=0 なので、$ f'(0)=5+0=5
x=0代入したら終わらん？
多項式は公開されない。公開されるのは多項式にx座標をぶちこんだ結果得られるy座標だけで、多項式を追加してもそれは同じだし、元のsecretはそのまま
ここまでの話をプロットするとこんな感じ↓
https://scrapbox.io/files/61946e1c1eaa9b001d0cd107.png
3. shareの更新手順
更新手順を一般化するとこんな感じ(n台のサーバにSSSの手法でshareが保存されている前提)
1. $ U_iはk-1個の乱数$ b_{ij}(j=1,2,...k-1)を生成し、式(2)(3)を満たすk-1次多項式を作る。
$ (2)b_i(z)=b_{i1}z^1+b_{i2}z^2+,...+b_{ik}z^{k-1}
$ (3)b_i(0)=0
2. 他の全ての$ U_jに$ u_{ij}=b_i(j)を送信する
3. $ U_jは$ u_{ij}を予め持っていたshareに追加する
$ (4)W_j^{(t)}=W_j^{(t-1)}+(u_{１j}+u_{2j}+...+u_{nj})
先ほどの例ではボブのみがshareの更新手順を踏んでいたが、キャロル、デイブも同様に1.~2.を実行する.
それぞれが作成した多項式をそれぞれg(x)、h(x)、k(x)とすると更新後にできる新しい多項式は以下のようになる.
$ f'(x) = f(x) + g(x) + h(x) + k(x)
これにより、ボブ、キャロル、デイブの古いshare(f(2),f(3),f(4))はそれぞれ意味を持たない
ディーラーを必要とせず再分配している実態は、各メンバーがディーラーとなり、公平な環境を作っているということDKG(Distributed Key Generation)と呼ばれる手法.
古い多項式は、更新後も有効なのでは?
更新前と更新後では、秘密情報のシェア生成の多項式が異なるため、たとえ更新前のシェアと更新後のシェアを合わせて閾値値分だけ集めたとしても、多項式を復元できないので秘密情報が漏洩することはない。 つまりshareの更新によって，漏洩した更新前のシェアは役に立たなくなる
閾値がそのままならば、安全性は低下するのでは？
この方法で、閾値も変更することができる。ただし、更新前のシェアを消さずに取っておくと、更新の意味がなくなるので注意が必要
4. グループへの再帰
例:Aliceがグループに復帰したい
Alice(x=1)に合わせて、g(1)=0となるようにg(x)を作成し、上述の更新手順に従ってブロードキャストする。
他のメンバーも同様
https://scrapbox.io/files/61967d94c578d2001d240036.png
AliceのID(x座標)が不明になったらshareを作り直せばいい
5. PVSS:Proactive Verifiable Secret Sharing
更新段階で嘘の情報を追加する攻撃に対する対処法
あるサーバP_iが(3)式を満たさない多項式を作成し、配布した場合にsecretが復元できない。
この事象に対処するため、shareの更新作業にVSS的な改善を加える
1. サーバP_iはk-1個の乱数を生成し、式(5)(6)を満たすk-1次方程式を作る。
$ (5)b_i(z)=b_{i1}z^1+b_{i2}z^2+,...+b_{ik}z^{k-1}
$ (6)ε_{im}=g^{b_{im}}
(6)式は(5)式の係数コミットメント
2. サーバ$ P_iは他の全てのサーバ$ P_jに対してshare$ u_{ij}=b_i(j)と$ e_{ij}=ENC_j(u_{ij})をブロードキャストする。
ここで、$ ENC_Rは受信者Rとしたときに、Rの公開鍵で暗号化することを示す.つまりコミットメントを公開鍵で暗号化している
shareを公開鍵暗号方式で暗号化しているのは、秘匿性のため
3. サーバ$ P_iは$ VSS_i^{(t)}=(i,t,ε_{im},e_{ij})と$ SIG_i(VSS_i^{(t)})をブロードキャストする
ここで、$ SIG_Sは送信者をSとした時に、Sの秘密鍵で署名することを示すつまり、VSSの署名を作成してる
コミットメントをデジタル署名したりしてるのは、それを$ P_iが作成したことを証明するため
4. サーバP_iは送られてきた情報$ e_{ij}を復号し、以下の式(7)で検証する
$ (7)g^{u_{ij}}=(ε_{j1})^i(ε_{j2})^{i^2}...(ε_{jk})^{i^k}
ここは,VSSの検証と同じ作業
5. 正確な情報と判断したら、送られてきた情報を保持し、検証が通ったことを他のサーバにブロードキャストする
全てのサーバの検証が通ったら保持していた$ b_j(i)を加える。
検証が通らなかったら、不正なサーバから送られる$ b_iを使用しない。
復元時に不正な分散情報を提出するサーバに対する対処法
1. shareの生成時、その生成者は検証鍵$ y_i^{(t)}=g^{W_i^{(t)}}を公開する。
2. 分散情報の更新を行うとき、(3)式または(6)式において各サーバは以下の(8)式によって検証鍵の更新を行い、公開する。
$ (8)y_i^{(t)}=y_i^{(t-1)}*(g^{(u_{1i})}*g^{(u_{2i})}*...g^{(u_{ni})})
3. 秘密情報の復元時、復元者は集めた分散情報を検証鍵で検証を行うことで分散情報が正しいものか判別する。
参考文献